package 剑指Offer.medium;

public class 二维数组中的查找 {

    class Solution2 {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            int rowSize = matrix.length;
            int colSize = matrix[0].length;
            if (target < matrix[0][0] || target > matrix[rowSize - 1][colSize - 1]) {
                return false;
            }
            int i = rowSize - 1;
            for (; i >= 0; i--) {
                if (matrix[i][colSize - 1] < target) break;
            }
            i++;
            for (int j = 0; j < colSize - 1; j++) {
                if (matrix[i][j] == target) return true;
            }
            return false;
        }
    }

    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            int rowSize = matrix.length;
            int colSize = matrix[0].length;
            if (target < matrix[0][0] || target > matrix[rowSize - 1][colSize - 1]) {
                return false;
            }
            int i = 0, j = colSize - 1;
            while (i < rowSize && j >= 0) {
                if (matrix[i][j] == target) {
                    return true;
                } else if (matrix[i][j] < target) {
                    i++;
                } else {
                    j--;
                }
            }
            return false;
        }
    }
}
